This invention relates to the field of computer systems. More particularly, a system and methods are provided for pre-fetching data during execution of a program, and thereby increasing caching efficiency.
Caching is often used to make execution of a computer program faster and more efficient. In particular, because main memory (e.g., RAM) is slower than processor cache memory, and secondary memory (e.g., disk) is even slower than main memory, having necessary memory contents (e.g., instructions) in cache memory rather than main or secondary memory can allow those contents to be accessed and used faster.
The more applicable the principles of spatial locality and temporal locality are, the greater the benefits of caching. Temporal locality dictates that when a particular piece of information (e.g., data, instruction) is accessed, it is likely to be accessed again. Spatial locality dictates that when one piece of information is accessed, nearby information is likely to be accessed also.
A computer program may be logically divided into a series of basic blocks. A basic block is a set of one or more instructions, wherein all the instructions will be executed or none of them will be executed. In other words, once the path of execution of a program leads to the first instruction of a basic block, it is certain that all of the instructions in that basic block will be executed. According to the principles of spatial and temporal locality, when a particular basic block is executed, it is likely to be executed again, and execution of one basic block makes execution of another basic block likely (e.g., the subsequent block in the program).
Within a basic block, various data elements (e.g., variables, arrays, constants) may be read or written to. However, it cannot be assumed that each time a basic block is executed, the same memory location from which data was retrieved the last time will be accessed again. The actual memory locations corresponding to those data elements may vary between iterations of the basic block. For example, the index i of a data element c[i] may be incremented each time a basic block is executed. Thus, memory locations pertaining to c[i], then c[i+1], c[i+2], and so on are used in successive iterations.
Therefore, what is needed is a method and apparatus for facilitating the pre-fetching of data accessed in a basic block, that allow for variation in the memory locations corresponding to the data.